The following abbreviations and terms are herewith defined, at least some of which are referred to within the following description about the prior art and/or the present invention.
CSConvergence SensitiveECEqual CostlyECTEqual Cost TreeIEEEInstitute of Electrical and Electronics EngineersI-SIDBackbone Service IdentifierIS-ISIntermediate System to Intermediate System Routing ProtocolLLoadLSPLink State PDUMmaximal rounds for auto configured opaque ECT-ALGORITHMsMSTPMultiple Spanning Tree ProtocolμPmicroprocessorOUIOrganizationally Unique IdentifierPDUProtocol Data UnitPBBProvider Backbone BridgesPBB-TEProvider Backbone Bridge Traffic EngineeringQoSQuality of ServiceRSTPRapid Spanning Tree ProtocolRxReceiveSPBShortest Path BridgingSPTShortest Path TreeTThresholdTxTransmitVIDVLAN Identifier                Equal Cost Trees: Two trees are equal cost trees if they span from the same source node to the same set of destination nodes and they contain different paths having the same cost.        The ECT algorithm: The ECT algorithm is specified in IEEE Std. 802.1aq D2.5, “IEEE Standard for Local and Metropolitan Area Networks: Virtual Bridged Local Area Networks—Amendment 8: Shortest Path Bridging,” January 2010. The ECT algorithm is a Dijkstra algorithm plus a tie-breaking for multiple equal cost shortest paths. It might happen that there are no equal cost paths in the network at all, then in this case all the ECT algorithms result in the same tree, which is not a real ECT as the different trees do not contain a different paths with equal cost path.        End-to-End Cost: Each link of the network has its own cost, also referred to as a metric. The end-to-end cost is the sum of link metrics along the path between the source node and the destination node. We talk about equal cost if there are        Opaque ECT algorithm: The opaque ECT algorithm means that it is defined outside of IEEE 802.1aq.        Equal Costliness: Equal Costliness is an indicator on whether or not the topology of the network contains a lot of equal cost paths (e.g., more than 30% of the paths have equal cost to another path).        Path ID: Path ID is a sorted list (in ascending lexicographic order) of the IDs of the links that the path traverses, which is specified by IEEE 802.1aq. Having a prefix before the Path ID and setting the prefix based on a function of load as discussed below is not part of the standard.        
There is a significant effort taking place today to enhance Ethernet networks so they are able to support carrier grade services and data center applications in addition to the many currently supported services and applications. In this regard, IEEE 802.1Qay PBB-TE “Provider Backbone Bridge Traffic Engineering” has been defined to support point-to-point and point-to-multipoint traffic engineered services. Furthermore, IEEE 802.1Qay PBB-TE has been defined to provide protection switching for point-to-point services thus making 50 ms failover time achievable. The contents of IEEE 802.1Qay PBB-TE are hereby incorporated herein by reference.
However, the only control protocols currently available for multipoint-to-multipoint services, which are also referred to as multipoint services, are RSTP and MSTP. Fortunately, there is an ongoing standardization project in IEEE known as Shortest Path Bridging (SPB) which defines a novel control protocol for bridged networks based on link state principles and in particular IS-IS. SPB not only supports multipoint services but also supports point-to-point services and point-to-multipoint services. This standardization project resulted in IEEE Std. 802.1aq D2.5, “IEEE Standard for Local and Metropolitan Area Networks: Virtual Bridged Local Area Networks—Amendment 8: Shortest Path Bridging,” January 2010. The contents of IEEE Std. 802.1aq D2.5 also referred to herein as “SPB” or “the standard SPB” are hereby incorporated by reference.
The main goal of SPB is to use the shortest path for frame forwarding and thus improve the overall utilization of the network by using links which are otherwise blocked by the spanning tree protocols (e.g., RSTP, MSTP). Nevertheless, SPB does not currently implement Traffic Engineering which for example is used to determine forwarding paths for traffic flows to meet certain criteria such as meeting QoS requirements or avoiding network congestion.
In addition, in a SPB network there might be multiple paths with the same end-to-end cost between a pair of bridges (nodes). To meet the congruency requirements of Shortest Path Trees (SPTs), the Dijkstra algorithm used by IS-IS for shortest path computation is extended to include a tie-breaking rule. To enable the tie-breaking rule, a Path ID has been introduced which is a sorted list (in ascending lexicographic order) of IS-IS Bridge IDs that the path traverses including the endpoint nodes. The extended Dijkstra algorithm selects the path with the lowest Path ID from multiple equal cost paths. To take advantage of multiple equal cost paths, SPB defines 16 Bridge ID shuffling algorithms, thus different paths become the one having the lowest Path ID for the different algorithms. The SPTs comprised of equal cost paths are called Equal Cost Trees (ECT). The shuffling algorithm and thus the SPT Set computed with it is identified by a unique standard ECT-ALGORITHM comprised of an OUT and an 8-bit index value. A VLAN identified by a Base VID is then assigned to a standard ECT-ALGORITHM by means of configuration in the SPB network, i.e. the STP Set thus the forwarding paths used by a VLAN. Furthermore, an I-SID which is a backbone service identifier is then assigned to a Base VID in Provider Backbone Bridge (PBB) networks. The traffic assignment and spreading on the 16 SPT Sets is configurable by means management actions.
Referring to FIG. 1 (PRIOR ART), there is a diagram of an exemplary SPB network 100 which has multiple traditional nodes 102 interconnected to one another by multiple links 104. The diagram provides a visual representation of SPB's multi-path routing features where all 16 standard individual shortest paths (see highlighted links 104) are superimposed on the SPB network 100 between a given pair of nodes 102 (1st node 102 and 20th node 102). The existing SPB's solution is only able to take advantage of 16 equal cost paths, nevertheless the physical topology of the network 100 may provide more than 16 equal cost paths. Furthermore, the pseudo random 16 Bridge ID shuffling algorithms specified in SPB may result in hot links or hot nodes, which are overloaded or heavily loaded with traffic. That is it may happen that the traffic is not distributed as evenly on the links 104 of the network 100 as it would otherwise be possible without the hot links or hot nodes. In addition, it would be desirable to use each and every link 104 of the network 100 for traffic forwarding, which is not necessarily supported by SPB.
Furthermore, SPB requires the use of the shortest path which might not be the optimal path in the network 100 if the aim is to have a balanced utilization of the network links 104. In other words, the aim of traffic engineering is to create as much as possible a uniform distribution of the traffic in the network 100, for which the shortest path forwarding is not always the most expedient. Thus, traffic engineering may deviate from shortest path forwarding to some extent to achieve better overall network utilization, which is not supported by the current SPB. In addition to this, the use of multiple ECTs is not automatic since it has to be configured, thus traffic spreading requires management actions and planning in advance. In view of the foregoing, it can be seen that there has been and still is a need to address the aforementioned shortcomings and other shortcomings associated with the current SPB. This need and other needs are satisfied by the present invention.